{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://hardcore.feishu.cn/docs/doccnp9v7IljXiJ5FpNT1ipLhlR\n",
    "- https://www.bilibili.com/video/BV1FL4y1j7Up"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 0. 前言\n",
    "\n",
    "磁盘kv代表leveldb：[Leveldb源码解读(一)](https://hardcore.feishu.cn/docs/doccnqc6VrpZk2JXSTcNr3Pq7Eb#a2ikGT)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Redis准备"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 简介"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Redis(REmote DIctionary Server)** 是一个开源（BSD许可）的，内存中的数据结构存储系统，它可以用作数据库、缓存和消息中间件。需要注意他和leveldb的区别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 特性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 性能高\n",
    "- 丰富的数据类型\n",
    "- 支持事务\n",
    "- 内建replication及集群\n",
    "- 支持持久化\n",
    "- 单线程，原子性操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 源码编译与调试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "源码下载\n",
    "- git地址：https://github.com/redis/redis/tree/5.0\n",
    "- 或者这里 Index of /releases/\n",
    "- wget也可以下载"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! wget https://github.com/redis/redis/archive/refs/tags/6.2.14.tar.gz\n",
    "! tar xzf redis-6.2.14.tar.gz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "执行编译\n",
    "- 修改配置文件中的`daemon`为`yes`\n",
    "- 禁用`gcc`编译优化，将makefile文件中`OPTIMIZATION?=-O2`修为`-O0`，可直接使用源码包下的二进制程序\n",
    "> redis-6.2.14/src/Makefile\n",
    "- `gdb redis-server [conf]`，配合gdb相关命令\n",
    "- 也可以直接开启`server.c`的`main`测试函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! sudo apt-get install pkg-config\n",
    "! cd ../redis-6.2.14 && make -j32"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "redis-server: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=a79a633e777602bb48d2a6e845da475409607e27, for GNU/Linux 3.2.0, with debug_info, not stripped\n"
     ]
    }
   ],
   "source": [
    "! cd ../redis-6.2.14/src && file redis-server"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! sudo apt-get install tcl tcl-dev\n",
    "! make test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 压测\n",
    "\n",
    "Redis-benchmark是官方自带的Redis性能测试工具，可以有效的测试Redis服务的性能。\n",
    "- `redis-benchmark [-h <host>] [-p <port>] [-c <clients>] [-n <requests]> [-k <boolean>]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. 基本数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 简单动态字符串(SDS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "redis为了节省内存，针对不同长度的数据采用不同的数据结构。如下共五种，但`SDS_TYPE_5`并不使用，因为该类型不会存放数据长度，每次都需要进行分配和释放："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "c"
    }
   },
   "outputs": [],
   "source": [
    "// redis-6.2.14/src/sds.h\n",
    "\n",
    "#define SDS_TYPE_5  0\n",
    "#define SDS_TYPE_8  1\n",
    "#define SDS_TYPE_16 2\n",
    "#define SDS_TYPE_32 3\n",
    "#define SDS_TYPE_64 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以`type=1`为例："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "c"
    }
   },
   "outputs": [],
   "source": [
    "// redis-6.2.14/src/sds.h\n",
    "\n",
    "typedef char *sds;\n",
    "\n",
    "/* Note: sdshdr5 is never used, we just access the flags byte directly.\n",
    " * However is here to document the layout of type 5 SDS strings. */\n",
    "struct __attribute__ ((__packed__)) sdshdr5 {\n",
    "    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */\n",
    "    char buf[];\n",
    "};\n",
    "struct __attribute__ ((__packed__)) sdshdr8 {\n",
    "    uint8_t len; /* used */\n",
    "    uint8_t alloc; /* excluding the header and null terminator */\n",
    "    unsigned char flags; /* 3 lsb of type, 5 unused bits */\n",
    "    char buf[]; // 变长数据\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 关于结构体内存对齐, 配置clangd, 会有智能提示; 或者使用`offsetof` ,见[01](./01/main.cpp)\n",
    "\n",
    "![01](./images/01.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 空间扩容"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 当前有效长度>=新增长度，直接返回\n",
    "- 更新之后，判断新旧类型是否一致：\n",
    "  - 一致使用`realloc`，否则使用`malloc`+`free`\n",
    "    - 当前有效长度>=新增长度，直接返回\n",
    "- 增长步长：\n",
    "  - 新增后长度小于预分配长度(1024*1024)，扩大一倍；\n",
    "  - 新增后长度大于等于预分配的长度，每次加预分配长度(减少不必要的内存)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "c"
    }
   },
   "outputs": [],
   "source": [
    "// redis-6.2.14/src/sds.h\n",
    "\n",
    "#define SDS_MAX_PREALLOC (1024*1024)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "c"
    }
   },
   "outputs": [],
   "source": [
    "// redis-6.2.14/src/sds.c\n",
    "\n",
    "/* Enlarge the free space at the end of the sds string so that the caller\n",
    " * is sure that after calling this function can overwrite up to addlen\n",
    " * bytes after the end of the string, plus one more byte for nul term.\n",
    " *\n",
    " * Note: this does not change the *length* of the sds string as returned\n",
    " * by sdslen(), but only the free buffer space we have. */\n",
    "sds sdsMakeRoomFor(sds s, size_t addlen) {\n",
    "    void *sh, *newsh;\n",
    "    size_t avail = sdsavail(s);\n",
    "    size_t len, newlen, reqlen;\n",
    "    char type, oldtype = s[-1] & SDS_TYPE_MASK;\n",
    "    int hdrlen;\n",
    "    size_t usable;\n",
    "\n",
    "    /* Return ASAP if there is enough space left. */\n",
    "    //// 检查可用空间\n",
    "    if (avail >= addlen) return s; // 如果当前可用空间 avail 大于或等于所需增加的长度 addlen，直接返回原字符串\n",
    "\n",
    "    //// 计算新长度\n",
    "    len = sdslen(s); // 计算当前字符串长度 len\n",
    "    sh = (char*)s-sdsHdrSize(oldtype);\n",
    "    reqlen = newlen = (len+addlen); // 计算请求的新长度 reqlen\n",
    "    assert(newlen > len);   /* Catch size_t overflow */ // 确保 newlen 大于 len，以防止 size_t 溢出\n",
    "    // 根据情况决定增长策略\n",
    "    if (newlen < SDS_MAX_PREALLOC) // 如果 newlen 小于 SDS_MAX_PREALLOC，则将其翻倍\n",
    "        newlen *= 2;\n",
    "    else  // 否则，增加 SDS_MAX_PREALLOC\n",
    "        newlen += SDS_MAX_PREALLOC;\n",
    "\n",
    "    //// 处理类型变化\n",
    "    type = sdsReqType(newlen);\n",
    "\n",
    "    /* Don't use type 5: the user is appending to the string and type 5 is\n",
    "     * not able to remember empty space, so sdsMakeRoomFor() must be called\n",
    "     * at every appending operation. */\n",
    "    if (type == SDS_TYPE_5) type = SDS_TYPE_8;\n",
    "\n",
    "    hdrlen = sdsHdrSize(type);\n",
    "    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */\n",
    "    // 判断 oldtype 和新类型 type 是否一致\n",
    "    if (oldtype==type) { // 如果一致，使用 s_realloc_usable 重新分配内存\n",
    "        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);\n",
    "        if (newsh == NULL) return NULL;\n",
    "        s = (char*)newsh+hdrlen;\n",
    "    } else { // 如果不一致，使用 s_malloc_usable 分配新内存并复制内容，最后释放旧内存\n",
    "        /* Since the header size changes, need to move the string forward,\n",
    "         * and can't use realloc */\n",
    "        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);\n",
    "        if (newsh == NULL) return NULL;\n",
    "        memcpy((char*)newsh+hdrlen, s, len+1);\n",
    "        s_free(sh);\n",
    "        s = (char*)newsh+hdrlen;\n",
    "        //// 更新头部信息\n",
    "        // 更新新分配内存的头部信息\n",
    "        s[-1] = type;\n",
    "        sdssetlen(s, len);\n",
    "    }\n",
    "    // 设置新的类型和可用空间\n",
    "    usable = usable-hdrlen-1;\n",
    "    if (usable > sdsTypeMaxSize(type))\n",
    "        usable = sdsTypeMaxSize(type);\n",
    "    sdssetalloc(s, usable);\n",
    "    return s;\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "C++17",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
